package cn.suchan.jianzhi.q40_array;

import java.util.ArrayList;

/**
 * 知识点：数组中只出现一次的数字
 * 题目描述
 * 一个整型数组里除了两个数字之外，其他的数字都出现了两次。
 * 请写程序找出这两个只出现一次的数字。
 *
 * @author suchan
 * @date 2019/06/04
 */
public class Solution {
    /**
     * num1,num2分别为长度为1的数组。传出参数
     * 将num1[0],num2[0]设置为返回结果
     * <p>
     * 一个个元素遍历比较
     * </p>
     *
     * @param array
     * @param num1
     * @param num2
     */
    public void FindNumsAppearOnce(int[] array, int num1[], int num2[]) {
        if (array.length <= 0 || array == null) {
            return;
        }
        int[] temp = new int[2];
        int t = 0;
        for (int i = 0; i < array.length; i++) {
            int count = 0;
            for (int j = 0; j < array.length; j++) {
                if (array[i] != array[j]) {
                    count++;
                }
            }
            if (count == array.length - 1) {
                temp[t] = array[i];
                t++;
            }
        }

        num1[0] = temp[0];
        num2[0] = temp[1];
    }

    /**
     * 利用异或的特性，即：
     * ① 0^a=a; a^0=a
     * ② a^a=0
     *
     * <p>
     * 题目中表明，该数组中除了两个只出现一次的数字之外，其他数字都出现两次，
     * 那么，如果对数组中所有数字进行一次异或运算，得到的值就是这两个只出现一次的数字异或的结果。
     * </p>
     *
     * <p>
     * 1、思路：
     * (1)对于出现两次的元素，使用“异或”操作后结果肯定为0，
     * 那么我们就可以遍历一遍数组，对所有元素使用异或操作，那么得到的结果就是两个出现一次的元素的异或结果。
     * (2)因为这两个元素不相等，所以异或的结果肯定不是0，
     * 也就是可以在异或的结果中找到一位不为0的位，例如异或结果的最后一位不为0。
     * (3)这样我们就可以根据这个不为0的二进制位，将原数组元素分为两组：一组该位全为1，另一组该位全为0。
     * (4)再次遍历原数组，最后一位为0的一起异或，最后一位为1的一起异或，两组异或的结果分别对应着两个结果。
     * 2、复杂度：
     * （1）时间复杂度：第一次循环，将所有元素异或得到对应结果，时间开销为O(n)；
     * 第二次循环，找出第一次异或结果为1的位，时间开销为O(32)；
     * 第三次循环，根据为1的位将元素分为两组进行异或得到两个结果，时间复杂度为O(n)，
     * 所以总的时间复杂度为T(n) = 2*O(n)+O(32) = O(n)。
     * （2）空间复杂度：常数，因为只分配了两个空间用于结果的保存，因此空间复杂度为常数。
     * </p>
     *
     * @param array
     * @param num1
     * @param num2
     */
    public void FindNumsAppearOnce1(int[] array, int num1[], int num2[]) {

        // 所有数异或的结果  0^a=a
        int result = 0;
        for (int i = 0; i < array.length; i++) {
            result ^= array[i];
        }

        // 获取该异或结果中从左开始第一位为1的二进制位
        int index = 0;
        // 注意，int类型为32位
        for (int i = 0; i < 32; i++) {
            if (((result >> i) & 1) == 1) {
                index = i;
                break;
            }
        }

        // 将数组中的所有数字分为两类（因为两个数异或结果为1，则表明该位上有一位数是0，一位数是1），
        // 一类是与异或结果左边第一位的位置同为1的数，另一类则不同的数
        // 这两类数之间进行异或的结果就是想要找的只出现一次的数
        for (int i = 0; i < array.length; i++) {
            if (((array[i] >> index) & 1) == 1) {
                num1[0] ^= array[i];
            } else {
                num2[0] ^= array[i];
            }
        }

    }

    /**
     * @param array
     * @param num1
     * @param num2
     */
    public void FindNumsAppearOnce2(int[] array, int num1[], int num2[]) {
        if (array.length <= 0 || array == null) {
            return;
        }

        ArrayList<Integer> list = new ArrayList<>();
        for (Integer a : array) {
            if (list.contains(a)) {
                list.remove(a);
            } else {
                list.add(a);
            }
        }

        num1[0] = list.get(0);
        num2[0] = list.get(1);
    }

    public static void main(String[] args) {
        int[] arr = {2, 4, 3, 6, 3, 2, 5, 5};
        int[] result1 = new int[1];
        int[] result2 = new int[1];

        Solution solution = new Solution();
        solution.FindNumsAppearOnce2(arr, result1, result2);

        System.out.println("result1==>" + result1[0]);
        System.out.println("result2==>" + result2[0]);
    }
}
